Insert Interval
Medium
Question
intervals is a list of non-overlapping intervals that are sorted by their start values.
Insert a new interval, new_interval, into intervals so that the resulting list is still non-overlapping and sorted.
Input: intervals = [[1, 3], [5, 7]], new_interval = [4, 6]
Output: [[1, 3], [4, 7]]
[4, 6] overlaps with [5, 7].
Input: intervals = [[0, 1], [3, 5], [6, 7]], new_interval = [1, 4]
Output: [[0, 5], [6, 7]]
[1, 4] overlaps with [0, 1] and [3, 5].
Input: intervals = [[1, 2], [3, 4]], new_interval = [5, 7]
Output: [[1, 2], [3, 4], [5, 7]]
[5, 7] is inserted into the list in sorted order.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
What is the resulting list of intervals if we have these inputs? intervals = [[1, 3], [5, 6], [8, 10]], new_interval = [2, 5]
[[8, 10], [1, 6]]
[[1, 6], [8, 10]]
[[1, 3], [2, 5], [5, 6], [8, 10]]
[[2, 5], [1, 3], [5, 6], [8, 10]]
Take a moment to understand the problem and think of your approach before you start coding.
